%===============================================================================
% Scan the input matrix in a zig-zag pattern in preparation for run-length
% encoding (RLE). 
% 
% 1. If input is a 2D array, scan it and output a 1D array i.e. a vector
%    holding the elements of the array scanned in a zigzag pattern
% 2. If input is a 1D array, traverse the 2D array in a zigzag pattern
%    and populate it with the data. 
%    'rows' is an optional argument for case (2) to determine 2D array 
%    dimensions i.e. rows x columns
%
% The implementation is a Finite State Machine (FSM) with 4 states, indicating 
% traversal direction in the matrix: east, south, southWest, northEast
%===============================================================================
function matrixOut = scanZigZag(matrixIn, rows)
  if nargin <2
    rows=1;
  end
  
  [M,N] = size(matrixIn);
  numElems = M*N;
  
  % data struct records are one-hot encoded states indicating move direction
  state = struct('east', 0, 'south', 0, 'southWest', 0, 'northEast', 0);

  mout = zeros(numElems, rows);

  % for each move through the array, update last move direction state and 
  % the coordinates

  x=1; y=1;  % begin in upper left corner
  state.northEast = 1;  % fake initial state to get moving in right direction
  
  vx = 1;
  mout(vx) = matrixIn(x,y);  % first output element

  for i=1:numElems-1  
      if (x == 1)  % at top row of array
        if (state.east ==1)
          state.east = 0;
	  state.southWest = 1;
          [x,y] = turn(x,y,'southWest');
        elseif (state.northEast ==1)
          state.northEast =0;
          if (y == N) % north-east corner
            state.south = 1;
            [x,y] = turn(x,y,'south');
          else
            state.east = 1;
            [x,y] = turn(x,y,'east');
          end
        end
      
      elseif (x == M) % at bottom row of array
	if (state.south ==1)
          state.south = 0;
          state.northEast = 1;
          [x,y] = turn(x,y,'northEast');
	elseif (state.east ==1)
          state.east = 0;
          state.northEast = 1;
          [x,y] = turn(x,y,'northEast');
        else
          state.southWest = 0;
          state.east = 1;
          [x,y] = turn(x,y,'east');
        end

      elseif (y == 1) % at left column of array
	if (state.south == 1)
          state.south = 0;
          state.northEast = 1;
          [x,y] = turn(x,y,'northEast');
        else
          state.southWest = 0;
          state.south = 1;
          [x,y] = turn(x,y,'south');
        end  

      elseif (y == N) % at right column of array
	if (state.northEast == 1)
          state.northEast = 0;
          state.south = 1;
          [x,y] = turn(x,y,'south');
        else
          state.south = 0;
          state.southWest =1;
          [x,y] = turn(x,y,'southWest');
        end  

      elseif (state.southWest ==1) % keep moving in same direction
          [x,y] = turn(x,y,'southWest');

      elseif (state.northEast ==1) % keep moving in same direction
          [x,y] = turn(x,y,'northEast');

      else
        disp('Error: we got lost in the matrix!');
      end   

      mout(i+1) = matrixIn(x,y);

      % debugging
      msg = sprintf('i: %d coord: (%d, %d)  value: %f',i,x,y,matrixIn(x,y));
      %disp(msg);
  end
  matrixOut = mout;


% Compute next set of coordinates based on direction of next move
function [x2,y2] = turn(x,y,direction)
  x2 = x;
  y2 = y;
  switch direction
    case {'s' 'S' 'south'}
      x2 = x+1;
    case {'e' 'E' 'east'}
      y2 = y+1;
    case {'ne' 'NE' 'northEast'}
      x2 = x-1;
      y2 = y+1;
    case {'sw' 'SW' 'southWest'}
      x2 = x+1;
      y2 = y-1;
    otherwise
      error ('invalid direction argument in turn function');
  end
